{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[toc]\n",
    "\n",
    "# 线性系统\n",
    "\n",
    "## 线性系统\n",
    "\n",
    "线性系统 -- 线性方程组\n",
    "\n",
    "线性 -- 未知数只能是**一次方项**\n",
    "\n",
    "## 高斯消元法\n",
    "\n",
    "$\\begin{cases} x+2y+4z=7 \\\\ 3x+7y+2z=-11 \\\\2x+3y+3z=1 \\end{cases} $\n",
    "\n",
    "增广矩阵\n",
    "\n",
    "$\\left (\n",
    "\\begin{array}{c:c}\n",
    "\\begin{matrix}\n",
    "1&2&4\\\\3&7&2\\\\2&3&3\n",
    "\\end{matrix}&\n",
    "\\begin{matrix}\n",
    "7\\\\-11\\\\1\n",
    "\\end{matrix}\n",
    "\\end{array}\n",
    "\\right )$\n",
    "\n",
    "行数代表方程数,列数代表未知变量数\n",
    "\n",
    "> 高斯消元法\n",
    "\n",
    "1. 某一行乘以非0常量\n",
    "2. 某一行加(减)另一行\n",
    "3. 交换两行位置\n",
    "\n",
    "> 高斯消元法\n",
    "\n",
    "1. 主元(pivot)为1 -- 每一行第一个非零元素\n",
    "2. 主元下方全为0\n",
    "\n",
    "$\\left (\n",
    "\\begin{array}{c:c}\n",
    "\\begin{matrix}\n",
    "1&2&4\\\\0&1&-10\\\\0&0&1\n",
    "\\end{matrix}&\n",
    "\\begin{matrix}\n",
    "7\\\\-32\\\\3\n",
    "\\end{matrix}\n",
    "\\end{array}\n",
    "\\right )$\n",
    "\n",
    "\n",
    "## 高斯-约旦消元法\n",
    "\n",
    "> 高斯消元法\n",
    "> 前向过程 -- 从上到下\n",
    "\n",
    "1. 选择最上的主元,化为1\n",
    "2. 主元下面的所有行减去主元所在行的某倍,使得主元下面所有元素为0\n",
    "\n",
    "$\\left (\n",
    "\\begin{array}{c:c}\n",
    "\\begin{matrix}\n",
    "1&2&4\\\\0&1&-10\\\\0&0&1\n",
    "\\end{matrix}&\n",
    "\\begin{matrix}\n",
    "7\\\\-32\\\\3\n",
    "\\end{matrix}\n",
    "\\end{array}\n",
    "\\right )$\n",
    "\n",
    "> 高斯-约旦消元法\n",
    "> 后向过程 -- 从下到上\n",
    "\n",
    "1. 选择最下主元\n",
    "2. 主元上面的所有行减去主元所在行的某倍,使得主元上面所有元素为0\n",
    "\n",
    "$\\left (\n",
    "\\begin{array}{c:c}\n",
    "\\begin{matrix}\n",
    "1&0&0\\\\0&1&0\\\\0&0&1\n",
    "\\end{matrix}&\n",
    "\\begin{matrix}\n",
    "-1\\\\-2\\\\3\n",
    "\\end{matrix}\n",
    "\\end{array}\n",
    "\\right )$\n",
    "\n",
    "## python实现高斯约旦消元法\n",
    "\n",
    "```python\n",
    "#Vector.py添加函数\n",
    "def underlying_list(self):\n",
    "    return self._values\n",
    "\n",
    "#LinearSystem.py\n",
    "\n",
    "from L04lesson.matrix import Matrix\n",
    "from L03lesson.vector import Vector\n",
    "\n",
    "class LinearSystem:\n",
    "\n",
    "    def __init__(self, A, b):\n",
    "\n",
    "        assert A.row_num() == len(b), \"row number of A must be equal to the length of b\"\n",
    "        self._m = A.row_num()\n",
    "        self._n = A.col_num()\n",
    "        assert self._m == self._n  # TODO: no this restriction\n",
    "\n",
    "        self.Ab = [Vector(A.row_vector(i).underlying_list() + [b[i]])\n",
    "                   for i in range(self._m)]\n",
    "\n",
    "    def _max_row(self, index_i, index_j, n):\n",
    "\n",
    "        best, ret = abs(self.Ab[index_i][index_j]), index_i\n",
    "        for i in range(index_i + 1, n):\n",
    "            if abs(self.Ab[i][index_j]) > best:\n",
    "                best, ret = abs(self.Ab[i][index_j]), i\n",
    "        return ret\n",
    "\n",
    "    def _forward(self):\n",
    "\n",
    "        n = self._m\n",
    "        for i in range(n):\n",
    "            # Ab[i][i]为主元\n",
    "            max_row = self._max_row(i, i, n)\n",
    "            self.Ab[i], self.Ab[max_row] = self.Ab[max_row], self.Ab[i]\n",
    "\n",
    "            # 将主元归为一\n",
    "            self.Ab[i] = self.Ab[i] / self.Ab[i][i]  # TODO: self.Ab[i][i] == 0?\n",
    "            for j in range(i + 1, n):\n",
    "                self.Ab[j] = self.Ab[j] - self.Ab[j][i] * self.Ab[i]\n",
    "\n",
    "    def _backward(self):\n",
    "\n",
    "        n = self._m\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # Ab[i][i]为主元\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                self.Ab[j] = self.Ab[j] - self.Ab[j][i] * self.Ab[i]\n",
    "\n",
    "    def gauss_jordan_elimination(self):\n",
    "\n",
    "        self._forward()\n",
    "        self._backward()\n",
    "\n",
    "    def fancy_print(self):\n",
    "\n",
    "        for i in range(self._m):\n",
    "            print(\" \".join(str(self.Ab[i][j]) for j in range(self._n)), end=\" \")\n",
    "            print(\"|\", self.Ab[i][-1])\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    A = Matrix([\n",
    "        [1,2,4],[3,7,2],[2,3,3],\n",
    "    ])\n",
    "    b = Vector([7,-11,1])\n",
    "    M = LinearSystem(A,b)\n",
    "    M.fancy_print()\n",
    "    M.gauss_jordan_elimination()\n",
    "    M.fancy_print()\n",
    "```\n",
    "\n",
    "\n",
    "## 行最简形式和线性方程组解的结构\n",
    "\n",
    "### 线性方程组解的解构\n",
    "\n",
    "1. 无解\n",
    "2. 无穷解\n",
    "3. 唯一解\n",
    "\n",
    "\n",
    "> 无解 \n",
    "> 行最简式A非零行 < 行最简式Ab非零行\n",
    "\n",
    "$\\left (\n",
    "\\begin{array}{c:c}\n",
    "\\begin{matrix}\n",
    "1&1&2\\\\0&4&-3\\\\0&0&0\n",
    "\\end{matrix}&\\begin{matrix}\n",
    "3\\\\10\\\\5\n",
    "\\end{matrix}\n",
    "\\end{array}\n",
    "\\right )$\n",
    "\n",
    "> 无穷解\n",
    "> 行最简式Ab非零行 < 未知数\n",
    "\n",
    "$\\left (\n",
    "\\begin{array}{c:c}\n",
    "\\begin{matrix}\n",
    "-1&2&3\\\\0&1&5\\\\0&0&0\n",
    "\\end{matrix}&\\begin{matrix}\n",
    "0\\\\0\\\\0\n",
    "\\end{matrix}\n",
    "\\end{array}\n",
    "\\right )$\n",
    "\n",
    "> 唯一解\n",
    "> 行最简式A非零行 = 未知数\n",
    "\n",
    "$\\left (\n",
    "\\begin{array}{c:c}\n",
    "\\begin{matrix}\n",
    "1&0&0\\\\0&1&0\\\\0&0&1\n",
    "\\end{matrix}&\\begin{matrix}\n",
    "2\\\\-3\\\\-4\n",
    "\\end{matrix}\n",
    "\\end{array}\n",
    "\\right )$\n",
    "\n",
    "### 阶梯型矩阵\n",
    "\n",
    "阶梯型矩阵 -- 也叫 行最简形式\n",
    "\n",
    "1. 每一非零行的第一个非零元素（称为主元）的列标，随着行标的递增而严格递增\n",
    "2. 零行（元素全为零的行）位于非零行的下方\n",
    "3. 主元所在列的其余元素全为零\n",
    "\n",
    "## 更一般的线性系统求解\n",
    "\n",
    "$\\left \\{\n",
    "\\begin{array}{rcl}\n",
    "x & -y & +2z & & +3u &=&1 \\\\\n",
    "-x & +y &   & +2w & -5u &=&5 \\\\\n",
    "x & -y & +4z & +2w & +4u &=&13 \\\\\n",
    "-2x & +2y & -5z & -w& -3u &=&-1 \n",
    "\\end{array}\n",
    "\\right . \\Rightarrow\n",
    "$\n",
    "\n",
    "$\n",
    "\\left ( \n",
    "\\begin{array}{c:c}\n",
    "\\begin{matrix}\n",
    " 1&-1 &0  &-2 &0 \\\\\n",
    " 0&0  &1  &1 &0 \\\\\n",
    " 0&0  &0  &0 &0 \\\\\n",
    " 0&0 &0 &0  &0\n",
    "\\end{matrix}\n",
    "&\n",
    "\\begin{matrix}\n",
    " -15\\\\ 5 \\\\ 2 \\\\  0\n",
    "\\end{matrix}\n",
    "\\end{array}\n",
    "\\right ) \\Rightarrow\n",
    "$\n",
    "\n",
    "$\\left \\{\n",
    "\\begin{array}{rcl}\n",
    "x & -y & +2w &=&-15 \\\\\n",
    "& z &+w &=&5 \\\\\n",
    "& & u &=&2\n",
    "\\end{array}\n",
    "\\right . \\Rightarrow\n",
    "$\n",
    "\n",
    "$\\left \\{\n",
    "\\begin{array}{rcl}\n",
    "x &=&-15  & +2w &+y \\\\\n",
    "& z&=& 5&-w  \\\\\n",
    "& & u &=&2\n",
    "\\end{array}\n",
    "\\right . \\Rightarrow\n",
    "$\n",
    "\n",
    "$\n",
    "\\left (\n",
    "\\begin{matrix}\n",
    "x\\\\z\\\\u\n",
    "\\end{matrix}\n",
    "\\right )=\\left (\n",
    "\\begin{matrix}\n",
    "-15\\\\5\\\\2\n",
    "\\end{matrix}\n",
    "\\right )+\\left (\n",
    "\\begin{matrix}\n",
    "1\\\\0\\\\0\n",
    "\\end{matrix}\n",
    "\\right )\\cdot{y}+\\left (\n",
    "\\begin{matrix}\n",
    "2\\\\-1\\\\0\n",
    "\\end{matrix}\n",
    "\\right )\\cdot{w}\n",
    "$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
